<html>
<title>Editing a Book</title>
<body>
<center>
<h1>Problem G</h1>
<h1>Editing a Book</h1>
</center>

<h2>Problem</h2>
<p>Modern writers do not use pens to write books. They enter the text directly on to the home PCs using MS Word and edit the text when necessary.
<p>After entering the text for a new book, a famous novelist desires to have a major rearrangement of the text he has prepared. He has identified passages in the text and numbered these passages. However the passages are not in proper sequence. He wants to use the minimum number of cut and paste operations of MS Word to edit the text and put the passages in proper order. He may do the operation either with one passage or with a number of passages occurring in a sequence. He needs a program for this purpose.
<p>The following example illustrates his problem. In order to edit the text containing 6 passages in the sequence P2, P4, P1, P5, P3, P6 so that the passages appear in the text in the proper sequence viz., P1, P2, P3, P4, P5, P6 he needs at least 2 cut and paste operations:
<ol>
<li>cut P1 and paste before P2 to get P1, P2, P4, P5, P3, P6</li>
<li>cut P3 and paste after P2 to get P1, P2, P3, P4, P5, P6</li>
</ol>

<p>Can you write a program for him?

<h2>Input</h2>
<p>The input may contain multiple test cases.
<p>For each test case, the first line contains two integers, the case number c and the total number n of passages.
<p>For simplicity, passages are represented by integers 1, 2, ..n. The input sequence of passages is given in n lines, each line containing one integer in the order in which the passages appear in the text before editing.
<p>The entire input set terminates with an input 0 for c.

<h2>Output</h2>
<p>For each test case in the input, print the test case number c and the total number k of cut and paste operations needed for the rearrangement of passages.
<p>Print the given sequence in one line. In the next k lines print successive changes in the sequence of passages due to application of k cut and paste operations.
<p>Print a blank line between outputs of two test cases.

<h2>Sample Input</h2>
<pre>
1 6
2
4
1
5
3
6
2 15
12
6
7
2
3
4
9
10
11
1
5
8
13
14
15
0
</pre>

<h2>Output for the Sample Input</h2>
<pre>
1 2
2 4 1 5 3 6
1 2 4 5 3 6
1 2 3 4 5 6
2 4
12 6 7 2 3 4 9 10 11 1 5 8 13 14 15
12 6 7 9 10 11 1 2 3 4 5 8 13 14 15
12 9 10 11 1 2 3 4 5 6 7 8 13 14 15
12 1 2 3 4 5 6 7 8 9 10 11 13 14 15
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
</pre>
<hr>
<b>Problem Source: </b>ACM/ICPC Regional Contest Asia-Kanpur 2001. Problem G. Editing a Book<br>
<b>Problem Archive: </b>None<br>
</body>
</html>